package StringMatch2;

public class StringMatch2 {

	public static void main(String[] args) {
		 String str1="goodgoogle";
         String str2="google";
         int index=match(str1,str2);
         System.out.println(index);
	}
	public static int[] getNext(char[] ch){
          int[] next = new int[ch.length];
          next[0]=-1;
          int j=0;
          int k=-1;
          while(j<ch.length-1){
        	  if(k==-1||ch[j]==ch[k]){
        		  j++;
        		  k++;
        		  next[j]=k;
        	  }
        	  else{
        		  k=next[k];
        	  }
          }
          return next;
		
	}
	public static int match(String str1,String str2){
		if(str1==null||str1.length()==0||str2==null||str2.length()==0){
			return -1;
		}
		char[] ch1 = str1.toCharArray();
		char[] ch2 = str2.toCharArray();
		int i=0;
		int j=0;
		int[] next = getNext(ch2);
		while(i<ch1.length&&j<ch2.length){
			if(j==-1||ch1[i]==ch2[j]){
				i++;
				j++;
			}
			else{
				j=next[j];
			}
		}
		if(j==ch2.length){
			return i-j;
		}
		else{
			return -1;
		}
		
	}

}
